package com.base.leetcode;

import com.base.dataStructure.queue.LinkedListQueue;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author: hdhao
 * @Create: 2023/4/1 - 13:27
 * @Version: v1.0
 */
//二叉树层序遍历
public class Leetcode102 {

    public static void main(String[] args) {
        //forEachBinaryTree();
        forEachBinaryTree2();
    }
    //简单遍历二叉树
    private static void forEachBinaryTree() {
        //一棵二叉树
        TreeNode root = new TreeNode(1,
                new TreeNode(2,
                        new TreeNode(4),new TreeNode(5)),
                new TreeNode(3,
                        new TreeNode(6),new TreeNode(7)));
        //创建一个队列
        LinkedListQueue<TreeNode> queue = new LinkedListQueue<>();
        //将根节点插入队列尾部
        queue.offer(root);
        //循环遍历队列(当队列不为空的时候,说明还未遍历完成)
        while (!queue.isEmpty()){
            //从队列头部获取节点并删除队列中的节点
            TreeNode n = queue.poll();
            System.out.print(n+" ");
            //判断该节点是否还有左节点
            if (n.left!= null){
                //如果还有左节点,将左节点加入队列中
                queue.offer(n.left);
            }
            //判断该节点是否还有右节点
            if (n.right!= null){
                //如果还有右节点,将右节点加入队列中
                queue.offer(n.right);
            }
        }
    }
    //输出的时候按层级输出
    private static void forEachBinaryTree2() {
        //一棵二叉树
        TreeNode root = new TreeNode(1,
                new TreeNode(2,
                        new TreeNode(4),new TreeNode(5)),
                new TreeNode(3,
                        new TreeNode(6),new TreeNode(7)));
        //创建一个队列
        LinkedListQueue<TreeNode> queue = new LinkedListQueue<>();
        //将根节点插入队列尾部
        queue.offer(root);
        //循环遍历队列(当队列不为空的时候,说明还未遍历完成)
        int c1 = 1;//当前层的节点数
        while (!queue.isEmpty()){
            int c2 = 0;//下一层节点数
            for (int i = 0;i<c1;i++){
                //从队列头部获取节点并删除队列中的节点
                TreeNode n = queue.poll();
                System.out.print(n+" ");
                //判断该节点是否还有左节点
                if (n.left!= null){
                    //如果还有左节点,将左节点加入队列中
                    queue.offer(n.left);
                    c2++;
                }
                //判断该节点是否还有右节点
                if (n.right!= null){
                    //如果还有右节点,将右节点加入队列中
                    queue.offer(n.right);
                    c2++;
                }
            }
            System.out.println();
            c1 = c2;
        }
    }

    /**
     * 二叉树层序遍历
     * @param root 根节点
     * @return 遍历后的返回值
     */
    public List<List<Integer>> levelOrder(TreeNode root){
        List<List<Integer>> result = new ArrayList<>();
        if (root == null){
            return result;
        }
        //创建一个队列
        LinkedListQueue<TreeNode> queue = new LinkedListQueue<>();
        //将根节点插入队列尾部
        queue.offer(root);
        //循环遍历队列(当队列不为空的时候,说明还未遍历完成)
        int c1 = 1;//当前层的节点数
        while (!queue.isEmpty()){
            List<Integer> level = new ArrayList<>();
            int c2 = 0;//下一层节点数
            for (int i = 0;i<c1;i++){
                //从队列头部获取节点并删除队列中的节点
                TreeNode n = queue.poll();
                level.add(n.val);
                //判断该节点是否还有左节点
                if (n.left!= null){
                    //如果还有左节点,将左节点加入队列中
                    queue.offer(n.left);
                    c2++;
                }
                //判断该节点是否还有右节点
                if (n.right!= null){
                    //如果还有右节点,将右节点加入队列中
                    queue.offer(n.right);
                    c2++;
                }
            }
            result.add(level);
            c1 = c2;
        }
        return result;
    }
}
